%!TEX program = xelatex
% 完整编译: xelatex -> biber/bibtex -> xelatex -> xelatex
\documentclass[lang=cn,11pt,a4paper]{elegantpaper}

% 本文档命令
\usepackage{array}
\usepackage{tikz}
\usepackage{pgf-pie}
\usepackage{pgfplots}
\usepackage{float}
\usepackage{amssymb}
\newcommand{\ccr}[1]{\makecell{{\color{#1}\rule{1cm}{1cm}}}}

\begin{document}

\title{Theoretical-Chapter3}

\author{周游}

\date{\zhtoday}

\maketitle


\section*{\uppercase\expandafter{\romannumeral1}}
Since $p(0) = 0$, assume $p(x) = ax^3+bx^2+cx$.

Since $s(x) = (2-x)^3$, we know $p(1) = s(1) = 1$, $p'(1) = s'(1) = -3$,
$p''(1) = s''(1) = 6$.

So $p(x) = 7x^3 - 18x^2 + 12x$ . Hence $p''(0) = -36 \neq 0$ , it's not a nature cubic spline.

\section*{\uppercase\expandafter{\romannumeral2}}
(a) For any $m_1 = f'(a)$ , for any $p_i = s|_{x_i,x_{i-1}} \in \mathbb{P}_2 $

we can uniquely determine $p_i$ from $p_i'(x_i), p_i(x_i), p_i(x_{i+1}) $, so we can get $s(x)$.

Since $m_1$ is arbitrary, $s(x) $ can't be determined  uniquely without additional condition.

\hspace*{\fill} 

(b) Assume $p_i(x) = ax^2 + bx + c$, we have $p_i'(x_i) = m_i, p_i(x_i) = f_i, p_i(x_{i+1}) = f_{i+1} $, so

\begin{equation*}
    \left\{
                 \begin{aligned}
                    p_i'(x_i) &= m_i    \\
                    p_i(x_i) &= f_i \\
                    p_i(x_{i+1}) &= f_{i+1}     \\
                 \end{aligned}
    \right.
    \Rightarrow
    \left\{
        \begin{aligned}
            a &= \frac{f[x_i,x_{i+1}]-m_i}{x_{i+1}-x_i}    \\
            b &= \frac{m_ix_{i+1}+m_ix_i-2x_if[x_i,x_i+1]}{x_{i+1}-x_i}  \\
            c &= f_i + \frac{x_if[x_i,x_{i+1}]-m_ix_{i+1}x_i}{x_{i+1}-x_i}   \\
         \end{aligned}       
    \right.
\end{equation*}

So $p_i(x) = \frac{f[x_i,x_{i+1}]-m_i}{x_{i+1}-x_i}x^2 + \frac{m_ix_{i+1}+m_ix_i-2x_if[x_i,x_i+1]}
{x_{i+1}-x_i}x + f_i + \frac{x_if[x_i,x_{i+1}]-m_ix_{i+1}x_i}{x_{i+1}-x_i}$

\hspace*{\fill} 

(c) When $m_i$ was given, we can determine $p_i$ from $m_i,f_i,f_{i+1}$, Then we can get $m_{i+1} = f'(i+1)$. 

By induction, we can get $m_2, \cdots, m_{n-1}$ if given $m_1$. 

\section*{\uppercase\expandafter{\romannumeral3}}
Assume $s_2(x) = a_3x^3 + a_2x^2 + a_1x + a_0$, so

\begin{equation*}
    \left\{
                 \begin{aligned}
                    s_2(0) &= s_1(0) = 1+c    \\
                    s_2'(0) &= s_1'(0) = 3c \\
                    s_2''(0) &= s_1''(0) =  6c    \\
                    s_2''(1) &= 0
                 \end{aligned}
    \right.
    \Rightarrow
    \left\{
        \begin{aligned}
            a_3 &=  -c  \\
            a_2 &= a_1 = 3c \\
            a_0 &=  1+c  \\
         \end{aligned}       
    \right.
\end{equation*}

So $s_2(x) = -cx^3 + 3cx^2 + 3cx + c + 1$.

When $s(1) = -1$, we can compute that $c = -\frac{1}{3} $.

\section*{\uppercase\expandafter{\romannumeral4}}
(a) Assume $s_1(x) = a_3x^3 + a_2x^2 + a_1x + a_0, s_2(x) = b_3x^3 + b_2x^2 + b_1x + b_0$. 

\begin{equation*}
    \left\{
            \begin{aligned}
                f(-1)   &= f(1) = 0 \\
                f(0)    &= 1   \\
                f''(-1)  &= f''(1) = 0
            \end{aligned}
    \right.
    \Rightarrow
    \left\{
        \begin{aligned}
            -a_3 &= b_3 = \frac{1}{2}   \\
            a_2 &= b_2 = -\frac{3}{2}  \\
            a_1 &= b_1 = 0 \\
            a_0 &= b_0 = 1  \\
         \end{aligned}       
    \right.
\end{equation*}

So the nature cubic spline is : 

\begin{equation*}
    s(x) = 
    \left\{
        \begin{aligned}
            -&\frac{1}{2} x^3 - \frac{3}{2} x^2 + 1      \qquad  if \ x \in [-1,0]       \\
            &\frac{1}{2} x^3 - \frac{3}{2} x^2 + 1       \qquad  if \ x \in [0,1]       \\
         \end{aligned}       
    \right.
\end{equation*}

(b) we can get : 

\begin{equation*}
    s''(x)
    \left\{
        \begin{aligned}
            -&3x-3      \qquad  if \ x \in [-1,0]       \\
            &3x-3      \qquad  if \ x \in [0,1]       \\
         \end{aligned}       
    \right.
    \Rightarrow
    \int_{-1}^1[s''(x)]^2dx = 6
\end{equation*}

(i) when g(x) be the quadratic polynomial, $g(x) = 1 - x^2$ , $\int_{-1}^1[g''(x)]^2dx = 8 > 6$

(ii) when g(x) = f(x), Since $f''(x) = -\frac{\pi^2}{4}\cos(\frac{\pi}{2}x) $, $\int_{-1}^1[g''(x)]^2dx = \frac{\pi^4}{16} > 6$

\section*{\uppercase\expandafter{\romannumeral5}}
(a) The recursive definition is : 

\begin{equation*}
    B_i^{n+1}(x) = \frac{x - t_{i-1}}{t_{i+n} - t_{i-1}}B_i^n(x) + \frac{t_{i+n+1} - x}{t_{i+n+1} - t_i}B_{i+1}^n(x)
\end{equation*}

and the base : 

\begin{equation*}
    B_i^0(x)
    \left\{
        \begin{aligned}
        &1 \qquad if \  x \in (t_{i-1},t_{i}]   \\
        &0 \qquad  otherwise \\
        \end{aligned}       
    \right.
\end{equation*}

So we get $B_i^1(x)$ as : 

\begin{equation*}
    B_i^1(x)
    \left\{
        \begin{aligned}
        &\frac{x - t_{i-1}}{t_{i} - t_{i-1}} \qquad &if \ x \in (t_{i-1},t_{i}]   \\
        &\frac{t_{i+1} - x}{t_{i+1} - t_i} \qquad &if \ x \in (t_{i},t_{i+1}] \\
        &0 \qquad &otherwise \\
        \end{aligned}       
    \right.
\end{equation*}

Then we get $B_i^2(x)$ as : 

\begin{equation*}
    B_i^2(x)
    \left\{
        \begin{aligned}
        &\frac{(x - t_{i-1})^2}{(t_{i+1} - t_{i-1})(t_{i} - t_{i-1})} \qquad &if \ x \in (t_{i-1},t_{i}]   \\
        &\frac{(x - t_{i-1})(t_{i+1} - x)}{(t_{i+1} - t_{i-1})(t_{i+1} - t_{i})} + 
        \frac{(t_{i+2} - x)(x - t_{i})}{(t_{i+2} - t_{i})(t_{i+1} - t_{i})} \qquad &if \ x \in (t_{i},t_{i+1}]   \\
        &\frac{(t_{i+2} - x)^2}{(t_{i+2} - t_{i})(t_{i+2} - t_{i+1})} \qquad &if \ x \in (t_{i+1},t_{i+2}]   \\
        &0 \qquad &otherwise \\
        \end{aligned}       
    \right.
\end{equation*}

\hspace*{\fill} 

(b) We get $\frac{d}{dx} B_i^2(x)$ as : 

\begin{equation*}
    \frac{d}{dx}B_i^2(x)
    \left\{
        \begin{aligned}
        &\frac{2(x - t_{i-1})}{(t_{i+1} - t_{i-1})(t_{i} - t_{i-1})} \qquad &if \ x \in (t_{i-1},t_{i}]   \\
        &\frac{t_{i-1} + t_{i+1} - 2x}{(t_{i+1} - t_{i-1})(t_{i+1} - t_{i})} + 
        \frac{t_{i} + t_{i+2} - 2x}{(t_{i+2} - t_{i})(t_{i+1} - t_{i})} \qquad &if \ x \in (t_{i},t_{i+1}]   \\
        &\frac{-2(t_{i+2} - x)}{(t_{i+2} - t_{i})(t_{i+2} - t_{i+1})} \qquad &if \ x \in (t_{i+1},t_{i+2}]   \\
        &0 \qquad &otherwise \\
        \end{aligned}       
    \right.
\end{equation*}

So $\lim\limits_{x \rightarrow t_i^-}\frac{d}{dx} B_i^2(x) = \frac{2}{t_{i+1} - t_{i-1}} 
= \lim\limits_{x \rightarrow t_i^+}\frac{d}{dx} B_i^2(x) $
, also $\lim\limits_{x \rightarrow t_{i+1}^-}\frac{d}{dx} B_i^2(x) = \frac{-2}{t_{i+2} - t_{i}} 
= \lim\limits_{x \rightarrow t_{i+1}^+}\frac{d}{dx} B_i^2(x) $

We can see it's continue. 

\hspace*{\fill} 

(c) Actually, only one $x^* \in (t_{i-1},t_{i+2})$ satisties $\frac{d}{dx} B_i^2(x) = 0$ , using the expression in (b) :

\begin{equation*}
    x^* = \frac{t_{i+2}t_{i+1} - t_{i}t_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}} \in (t_{i},t_{i+1})
\end{equation*}

(d) From (c), we know that the only possible extremums are located at $x^*, t_{i-1}, t_{i+2}$ .  

Since $B_i^2(t_{i-1}) = B_i^2(t_{i+2}) = 0$ , and $B_i^2(x^*) = \frac{t_{i+2} - t_{i-1}}{t_{i+2} + t_{i+1} - t_i - t_{i-1}} < 1 $ . 
So $B_i^2(x) \in [0,1)$

(e) Plot $B_i^2(x)$ for $t_i = i$ : 

\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{Bspline.png}
    \caption{Plot $B_i^2(x)$}
\end{figure}

\section*{\uppercase\expandafter{\romannumeral6}}
To proof $(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t-x)^2_+ = B^2_i(x)$ 

\begin{equation*}
    LHS = \frac{(t_{i+2}-x)^2_+ - (t_{i+1}-x)^2_+}{(t_{i+2}-t_{i+1})(t_{i+2}-t_{i})}
    - \frac{(t_{i+1}-x)^2_+ - (t_{i}-x)^2_+}{(t_{i+1}-t_{i})(t_{i+2}-t_{i})}
    - \frac{(t_{i+1}-x)^2_+ - (t_{i}-x)^2_+}{(t_{i+1}-t_{i})(t_{i+1}-t_{i-1})}
    + \frac{(t_{i}-x)^2_+ - (t_{i-1}-x)^2_+}{(t_{i}-t_{i-1})(t_{i+1}-t_{i-1})}
\end{equation*}

When $x < t_{i-1} $ or $ x > t_{i+2}$ , easy to get LHS = RHS = 0. 

When $x \in (t_{i-1},t_{i}] $, $LHS = \frac{(x - t_{i-1})^2}{(t_{i+1} - t_{i-1})(t_{i} - t_{i-1})}  = RHS$

When $x \in (t_{i-1},t_{i}] $, $LHS = \frac{(x - t_{i-1})(t_{i+1} - x)}{(t_{i+1} - t_{i-1})(t_{i+1} - t_{i})} + 
\frac{(t_{i+2} - x)(x - t_{i})}{(t_{i+2} - t_{i})(t_{i+1} - t_{i})}  = RHS$

When $x \in (t_{i-1},t_{i}] $, $LHS = \frac{(t_{i+2} - x)^2}{(t_{i+2} - t_{i})(t_{i+2} - t_{i+1})}  = RHS$ . Proved.

\section*{\uppercase\expandafter{\romannumeral7}}
Theorem on derivatives : 

\begin{equation*}
    \frac{d}{dx}B^n_i(x) = \frac{nB^{n-1}_i(x)}{t_{i+n-1}-t_{i-1}} - \frac{nB^{n-1}_{i+1}(x)}{t_{i+n}-t_i}
\end{equation*}

Define $int(B^n_i) = \frac{1}{{t_{i+n}-t_{i-1}}} \int_{t_{i-1}}^{t_{i+n}}B^n_i(x)dx$ . When n > 0, integral to both sides : 

\begin{equation*}
    \int_{t_{i-1}}^{t_{i+n}} \frac{d}{dx}B^n_i(x)dx = \frac{n\int_{t_{i-1}}^{t_{i+n-1}}B^{n-1}_i(x)dx}
    {t_{i+n-1}-t_{i-1}} - \frac{n\int_{t_{i}}^{t_{i+n}}B^{n-1}_{i+1}(x)dx}{t_{i+n}-t_i}
\end{equation*}

So

\begin{equation*}
    \begin{aligned}
        LHS &= B^n_i(t_{i+n}) - B^n_i(t_{i-1}) = 0 \\
            &= RHS  \\
            &= n (int(B_i^{n-1}) - int(B_{i+1}^{n-1}))
    \end{aligned}  
\end{equation*}

So $int(B_i^{n}) = int(B_{i+1}^{n})$ for all $n\in \mathbb{N},1 \leqslant i \leqslant N $ . 

So $int(B^n_i) = \frac{1}{{t_{i+n}-t_{i-1}}} \int_{t_{i-1}}^{t_{i+n}}B^n_i(x)dx = C(n)$ (C only depends on n) .  

It's independent of $i$ even if $t_i$ are not uniform.


\section*{\uppercase\expandafter{\romannumeral8}}
(a) When m = 4, n = 2, we need $\tau_2(x_i,x_{i+1},x_{i+2}) = [x_i,x_{i+1},x_{i+2}]x^4 $  .

the table of divided difference : 

\begin{table}[H]
    \begin{center}
    \begin{tabular}{l|c c r} 
      $x_i$         & $x_i^4$         &       &   \\
      $x_{i+1}$     & $x_{i+1}^4$     & $x_{i+1}^3+x_{i+1}^2x_i+x_{i+1}x_i^2+x_i^3$ &   \\
      $x{i+2}$      & $x_{i+2}^4$     & $x_{i+2}^3+x_{i+2}^2x_{i+1}+x_{i+2}x_{i+1}^2+x_{i+1}^3$ & $\sum\limits_{i\leqslant j\leqslant k\leqslant i+2 }x_jx_k $  \\
    \end{tabular}
    \end{center}
\end{table}
As a result, it can also express as : 

\begin{table}[H]
    \begin{center}
    \begin{tabular}{l|c c r} 
      $x_i$         & $\tau _4(x_i)$         &       &   \\
      $x_{i+1}$     & $\tau _4(x_{i+1})$     & $\tau _3(x_i,x_{i+1})$ &   \\
      $x{i+2}$      & $\tau _4(x_{i+2})$     & $\tau _3(x_{i+1},x_{i+2})$ & $\tau _2(x_i,x_{i+1},x_{i+2})$  \\
    \end{tabular}
    \end{center}
\end{table}
So we can get $\tau_2(x_i,x_{i+1},x_{i+2}) = [x_i,x_{i+1},x_{i+2}]x^4 $. 

(b) The recursive relation : 

\begin{equation*}
    \tau_{k+1}(x_1,\cdots,x_n,x_{n+1}) = \tau_{k+1}(x_1,\cdots,x_n) + x_{n+1}\tau_k(x_1,\cdots,x_n,x_{n+1})
\end{equation*}

We need to prove :

\begin{equation*}
    \tau_{m-n}(x_i,\cdots,x_{i+n}) = [x_i,\cdots,x_{i+n}]x^m
\end{equation*}

proof : By recursive relation : 

\begin{equation*}
    \begin{aligned}
         &\tau_{k+1}(x_1,\cdots,x_n) + x_{n+1}\tau_k(x_1,\cdots,x_n,x_{n+1}) \\
        =&\tau_{k+1}(x_1,\cdots,x_n,x_{n+1})    \\
        =&\tau_{k+1}(x_2,\cdots,x_{n+1}) + x_{1}\tau_k(x_1,\cdots,x_n,x_{n+1}) \\
    \end{aligned}     
\end{equation*}

So :

\begin{equation*}
    \begin{aligned}
        \tau_k(x_1,\cdots,x_n,x_{n+1}) =
        \frac{\tau_{k+1}(x_2,\cdots,x_{n+1})-\tau_{k+1}(x_1,\cdots,x_n)}{x_{n+1}-x_1}
    \end{aligned}     
\end{equation*}

For $\forall m \in \mathbb{N}^+ $ , when n = 0, $\tau_m(x_i) = [x_i]x^m $ is true. 

Assume it's true for n (n < m), consider n+1 : 

\begin{equation*}
    \begin{aligned}
        &\tau _{m-n-1}(x_i,\cdots,x_{i+n+1}) \\
        =& \frac{\tau_{m-n}(x_{i+1},\cdots,x_{i+n+1})-\tau_{m-n}(x_i,\cdots,x_n)}{x_{i+n+1}-x_i} \\
        =& \frac{[x_{i+1},\cdots,x_{i+n+1}]x^m - [x_i,\cdots,x_{i+n}]x^m}{x_{i+n+1}-x_i}    \\
        =& [x_i,\cdots,x_{i+n+1}]x^m
    \end{aligned}     
\end{equation*}

By induction, it's proved.

\end{document} 